package problem34;


//34. 二分模板
//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1, -1};
        int left = 0, right = nums.length-1;
        int[] ret = new int[2];
        //二分查找区间左端点
        while(left < right) {
            int mid = left + (right - left)/2;
            if(nums[mid] < target) {
                left = mid+1;
            }else {
                right = mid;
            }
        }
        //判断是否有结果
        if(nums[left] != target) return new int[]{-1, -1};
        else ret[0] = left;
        
        //二分查找区间右端点
        left = 0;
        right = nums.length-1;
        while(left < right) {
            int mid = left + (right - left +1)/2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid-1;
            }
        }
        ret[1] = left;
        return ret;
    }
}

/**
模板
二分查找区间左端点
while(left < right) {
    int mid = left + (right - left)/2;
    if(....) left = mid + 1;
    else right = mid;
}

二分查找区间右端点
while(left < right) {
    int mid = left + (right - left + 1)/2;
    if(....) left = mid;
    else right = mid-1;
}
 */